import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.TreeMap;


public class Ex5_5 {

	public Ex5_5() {}

	public static void main(String[] args) {
		Ex5_5 ex5 = new Ex5_5();
		TreeMap<String,ArrayList<String>> graph = 
				ex5.getGraph("C:\\Users\\josemfer\\Downloads\\dataset_59_5.txt");
		ArrayList<String> contigs = ex5.generateContigs(graph);
		ex5.writeFile(contigs);


	}

	private ArrayList<String> generateContigs(TreeMap<String,ArrayList<String>> aGraph) {
		ArrayList<String> startNodes = new ArrayList<String>();
		ArrayList<String> contigs = new ArrayList<String>();
		HashMap<String,Integer> inDegreeMap = getInDegree(aGraph);
		for (Entry<String,ArrayList<String>> entry : aGraph.entrySet()) {
			String node = entry.getKey();
			Integer inDegree =  
					inDegreeMap.get(node) == null ? 0 : inDegreeMap.get(node);
			ArrayList<String> outs = aGraph.get(node);
			Integer outDegree =   outs == null ? 0 : outs.size();
			if (outDegree > 1 || inDegree != 1) {		
				startNodes.add(node);
			}			
		}
		for (String node : startNodes) {
			ArrayList<String> outgoings = aGraph.get(node);
			for (int i=0;i<outgoings.size();i++) {
				String outgoing = outgoings.get(i);
				String contig = new String("");
				contig += node.substring(0,1);
				do {
					contig += outgoing.substring(0,1);
					ArrayList<String> outs = aGraph.get(outgoing);
					if (outs == null || outs.size() > 1 || startNodes.contains(outgoing)) {
						break;
					} else {
						outgoing = outs.get(0);
					}
				} while(true);
				contig += outgoing.substring(1,outgoing.length());
				contigs.add(contig);
			}
		}
		Collections.sort(contigs);
		return contigs;

		//System.out.println(startNodes);

	}



	private HashMap<String,Integer> getInDegree(TreeMap<String,ArrayList<String>> aGraph) {
		HashMap<String,Integer> inDegreeMap = new HashMap<String,Integer>(); 
		for (Entry<String,ArrayList<String>> entry : aGraph.entrySet()) {
			ArrayList<String> outgoings = entry.getValue();
			for (String outgoing : outgoings) {
				Integer indegree = inDegreeMap.get(outgoing);
				if (indegree == null) {
					inDegreeMap.put(outgoing, 1);
				} else {
					inDegreeMap.put(outgoing, indegree + 1);
				}
			}
		}
		return inDegreeMap;		
	}


	private TreeMap<String,ArrayList<String>> getGraph(String file) {		
		TreeMap<String,ArrayList<String>> graph = new TreeMap<String,ArrayList<String>>();	
		try {
			BufferedReader br = new BufferedReader(new FileReader(file));
			String line;		
			while ((line = br.readLine()) != null) {
				line = line.trim();				
				String prefix = line.substring(0,line.length()-1);
				String sufix = line.substring(1,line.length());
				ArrayList<String> outgoings = graph.get(prefix);
				if (outgoings == null) {
					outgoings = new ArrayList<String>();
					outgoings.add(sufix);
					graph.put(prefix, outgoings);
				} else {					
					outgoings.add(sufix);					
				}				
			}			
			br.close();
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		return graph;
	}



	private void writeFile(ArrayList<String> contigs) {
		Writer writer = null;
		String text = "";
		for (String contig  :contigs) {
			text += contig + "\n";
		}		
		
		try {
			writer = new BufferedWriter(new OutputStreamWriter(
					new FileOutputStream("C:\\Users\\josemfer\\Downloads\\ex5_4_out.txt"), "utf-8"));
			writer.write(text);
		} catch (IOException ex) {
			// report
		} finally {
			try {writer.close();} catch (Exception ex) {}
		}
	}



}
